題目:

Given the root of a binary tree, return the inorder traversal of its nodes' values.

給定一個binary tree,依中序遍歷(Inorder Traversal)的順序回傳裡面的值(用list)

到這裡,可能要先講一下二元樹(binary tree)
二元樹是長這樣的資料結構

一個node最多只能有兩個子node(left,right),最上層的node稱root,無子節點的node稱leaf
一種相當著名且重要的資料結構

認識二元樹很快,但真正需要時間理解及熟練的是它的搜尋法
分為兩種:深度優先搜尋(DFS)和廣度優先搜尋(BFS)

深度優先搜尋如其名,儘可能深入地探索樹的分支,當所在node所接的node都被探索過,就再返回上一個node,重複執行
以圖來看的話就是長這樣

廣度優先搜尋是即把同一層的node走訪完，再繼續向下一層搜尋，直到遍尋全部node
以圖來看的話就是長這樣

兩種方式在以後的程式都會用到,會特別提

接著是遍歷順序,主要分三種前序遍歷(Preorder Traversal),中序遍歷(Inorder Traversal),後序遍歷(Postorder Traversal)
前序遍歷:先拜訪父節點再拜訪左右子節點
中序遍歷:先拜訪左子節點，再拜訪父節點，最後拜訪右子節點
後序遍歷:先拜訪左右子節點，最後拜訪父節點

那我們回到題目,這題我是用dfs下去做

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: #防範一開始給的root就是None
            return []
        
        ans=[]
        
        def dfs(root,ans):
            if root.left!=None: #先拜訪左節點
                dfs(root.left,ans)
                
            ans.append(root.val) #再拜訪父節點
            
            if root.right!=None: #最後拜訪右節點
                dfs(root.right,ans)
                
            return ans #全拜訪過後回傳上一節點
            
        return dfs(root,ans)

以遞迴的方式走訪,且設一個空list存走訪的值
如上面的dfs定義,透過遞迴的方式深入探索樹的分支
依中序遍歷的方式向深處走訪,完全走訪完回到上一節點,不斷重複
完全跑完後就獲得我們要的陣列了
最後執行時間28ms(faster than 96.22%)

但是到這裡題目還沒結束,最下面寫了一行

Recursive solution is trivial, could you do it iteratively?

題目想要我們試試用迭代的的方式去做,我們接下這個挑戰

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: #防範一開始給的root就是None
            return []
            
        ans=[]
        path=[]
        
        while True:
        
            if root.left: #左有枝往左探勘
                path.append(root) #將node紀錄到path內,以便回傳
                root=root.left
                
            elif root.right: #右有枝往右探勘
                ans.append(root.val) #由於是中序遍歷,要先紀錄父節點值
                root=root.right      #又因為右枝探勘完就等於這個node已完全紀錄,故不存在path內
                
            else:
                ans.append(root.val) #到底端紀錄值
                
                if path==[]: #完全遍歷,結束程式
                    return ans
                    
                root=path.pop() #完全探索完,回上一節點
                
                if root.left: #回來若左枝在則切左枝,因為左枝在則代表我們是探索完左枝回來的
                    root.left=None  

設兩個空陣列,一個紀錄走訪值(ans),一個紀錄當一個node走訪完畢後要回傳的node(path)
又由於我是以模擬dfs的搜索方式,path會以stack的方式去做紀錄和取出(後進先出)
記得左邊的枝探索完要記得切枝(把探索完的枝變None)才可以讓程式換邊去探索(左枝完換右枝)
最後當path內沒東西,且也沒有枝可以探索的時候,就代表我們已經完全遍歷
由於這個程式實在有點難口述,所以主要資訊我都打在註解上
最後執行時間29ms(faster than 95.29%)

本題學習到的重點:二元樹(Binary Tree),深度優先搜尋(DFS),廣度優先搜尋(BFS)
那我們下題見